package com.study.tree;

import javax.swing.plaf.nimbus.NimbusLookAndFeel;

public class RedBlackTree {
    public static final int RED = -1;
    public static final int BLACK = 1;
    public static final Node NIL = new Node();
    private Node root;

    public void leftRotate(Node x){
//        左旋，父结点的改变情况只有 x,结点，y结点，y.l;
        Node y= x.r;
        x.r = y.l;
        if (y.l != NIL) y.l.p = x;
        y.p = x.p;
        if(x.p == NIL){
            root = y;
        }else if( x.p.l == x){
            x.p.l = y;
        }else{
            x.p.r = y;
        }
        x.p = y;
        y.l = x;
    }

    public void rightRotate(Node y){
//        与左旋类似
        Node x = y.l;
        y.r = x;
        if(x.r != NIL) x.r.p = y;
        x.p = y.p;
        if(y.p == NIL){
            root = x;
        }else if(y.p.l == y){
            y.p.l = x;
        }else{
            y.p.r = x;
        }
        y.p = x;
        x.r = y;
    }

    public void insert(Integer key){
        Node newNode = new Node(key,RED);
        if(root == null){
            root = newNode;
            newNode.color = BLACK;
            return;
        }
        Node cur = root;
        while (cur != NIL){
            if(cur.key >= key){
                if(cur.r == NIL){
                    cur.r = newNode;
                    newNode.p = cur;
                    break;
                }else {
                    cur = cur.r;
                }
            }else{
                if(cur.l == NIL){
                    cur.l = newNode;
                    newNode.p = cur;
                    break;
                }else{
                    cur = cur.l;
                }
            }
        }
        fixInsert(newNode);
    }

    public void delete(Integer key){
        Node x = find(key);
    }

    private Node find(Integer key){
        Node cur = root;
        while (cur != null && cur != NIL){
            if(cur.key == key) return cur;
            if(cur.key > key) cur = cur.r;
            else cur = cur.l;
        }
        return null;
    }

    private void fixInsert(Node z){
//        todo 恢复红黑树的性质
        while (z.p.color == RED ){
//            如果该结点的叔结点为 --红色  将它的父结点和叔结点变黑，将祖父结点变红。
//                如果叔结点为 黑色 -- 根据 左右结点判断。
//               1. * 左节点/右边结点 根据 插入结点树的颜色判断。
//               2. 最后一次旋转，通过将z的父结点上升，将它的祖父结点下降的旋转方式结束。
            if(z.p.p.l == z.p){
                //            父结点位于 左,叔结点在右边
                if(z.p.p.r.color == RED){
                    z.p.p.r.color = BLACK;
                    z.p.color = BLACK;
                    z.p.p.color = RED;
                    z = z.p.p;
//                    黑高不变 -->可能产生 2个红色结点相临
                }else{
                    if(z.p.r == z){
//                        左旋不改变黑高
                        leftRotate(z.p);
                    }
//                    交换，父节点，祖父节点颜色，右旋
                    z.p.p.color = RED;
                    z.p.color = BLACK;
                    rightRotate(z.p.p);

                }
            }else{
//                父结点位于右边,叔结点为红色
                if(z.p.p.l.color == RED){
                    z.p.p.l.color = BLACK;
                    z.p.color = BLACK;
                    z.p.p.color = RED;
                    z = z.p.p;
                }else{
                    if(z.p.l == z){
                        rightRotate(z.p);
                    }
                    z.p.p.color = RED;
                    z.p.color = BLACK;
                    leftRotate(z.p.p);
                }
            }
        }
    }

    private static class Node{
        public Node l;
        public Node r;
        public Node p;
        public Integer key;
        public int color;
        Node(){
            this.color = BLACK;
        }

        Node(int color){
            this.color = color;
            r = RedBlackTree.NIL;
            l = RedBlackTree.NIL;
            p = RedBlackTree.NIL;
        }

        Node(Integer key,int color){
            this(color);
            this.key = key;
        }
    }

    public static void main(String[] args){

    }

}
